class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long, vector<long>, greater<long>> pq;
        unordered_set<long> st;
        pq.push(1);
        st.insert(1);
        int ugly = 0;
        int k[3] = { 2, 3, 5 };
        for(int i = 0; i < n; ++i)
        {
            long cur = pq.top();
            pq.pop();
            ugly = (int)cur;
            for(int j = 0; j < 3; ++j)
            {
                long tmp = cur * k[j];
                if(!st.contains(tmp))
                {
                    pq.push(tmp);
                    st.insert(tmp);
                }
            }
        }
        return ugly;
    }
};
